package com.algorithm.example;

import com.algorithm.Utils.commonUtils.CommonUtils;
import lombok.Getter;
import org.springframework.stereotype.Component;

import java.util.Arrays;
import java.util.LinkedList;

/**
 * <p>
 * 递归
 * </p>
 *
 * @author lzt
 * @version 1.0
 * @since 2024/1/20 12:32
 */
@Component
public class Recursion {

    /**
     * 阶乘
     */
    public int factorial(int a) {
        if (a == 1 || a == 0) {
            return a;
        }
        return a * this.factorial(a - 1);
    }

    /**
     * 反向打印字符串
     */
    public void ReversePrint(String str) {
        ReversePrint(str, str.length() - 1);
    }

    private void ReversePrint(String str, int a) {
        if (a == -1) {
            return;
        }
        System.out.print(str.charAt(a));
        a -= 1;
        ReversePrint(str, a);
    }

    /**
     * 二分查找
     */
    public int dichotomy(int[] a, int target) {
        return dichotomy(a, target, 0, a.length - 1);
    }

    private int dichotomy(int[] a, int target, int i, int j) {
        if (i > j) {
            return -1;
        }
        int m = (i + j) >>> 1;
        if (target < a[m]) {
            j = m - 1;
        } else if (target > a[m]) {
            i = m + 1;
        } else {
            return m;
        }
        return dichotomy(a, target, i, j);
    }

    /**
     * 冒泡排序
     */
    public int[] bubbling(int[] a) {
        return bubbling(a, a.length - 1);
    }

    private int[] bubbling(int[] a, int j) {
        if (j == 0) {
            return a;
        }
        int target = 0;
        for (int i = 0; i < j; i++) {
            if (a[i] > a[i + 1]) {
                int item = a[i];
                a[i] = a[i + 1];
                a[i + 1] = item;
                target = i;
            }
        }
        return bubbling(a, target);
    }

    private int[] bubbling1(int[] a, int j) {
        if (j == 0) {
            return a;
        }
        for (int i = 0; i < j; i++) {
            if (a[i] > a[j]) {
                int item = a[i];
                a[i] = a[j];
                a[j] = item;
            }
        }
        return bubbling(a, --j);
    }

    public void insertionSort(int[] a) {
        insertionSort(a, 1);
    }


    /**
     * 插入排序
     */
    private void insertionSort(int[] a, int low) {
        if (low == a.length) {
            return;
        }
        int t = a[low];
        int i = low - 1; // 已排序区域指针

        while (i >= 0 && t < a[i]) { // 没有找到插入位置
            a[i + 1] = a[i]; // 空出插入位置
            i--;
        }

        // 找到插入位置
        a[i + 1] = t;
        insertionSort(a, low + 1);
    }

    /**
     * 斐波那契
     */
    public int fibonacci(int value) {
        if (value == 0) {
            return 0;
        }
        if (value == 1) {
            return 1;
        }

        return fibonacci(value - 1) + fibonacci(value - 2);
    }

    /**
     * 记忆法(备忘录) 斐波那契
     */
    public int fibonacciPlus(int a) {
        int[] cache = new int[a + 1];
        Arrays.fill(cache, -1); // 全部初始化为-1 -> 标记为没数据
        cache[0] = 0;
        cache[1] = 1;
        return memory(a, cache);
    }

    private int memory(int value, int[] cache) {
        if (cache[value] != -1) {
            return cache[value];
        }
        int x = memory(value - 1, cache);
        int y = memory(value - 2, cache);
        cache[value] = x + y;
        return cache[value];
    }

    /**
     * 归并排序
     */
    public void split(int[] B, int i, int j, int[] A) {
        if (j - i <= 1) {
            return;
        }
        int m = (i + j) >>> 1;

        // 递归
        split(A, i, m, B);
        split(A, m, j, B);

        // 合并
//        merge(B,i,m,j,A);
    }

    /**
     * 汉诺塔
     */
    public void towerHanoi(int n) {
        @Getter
        class Hanoi {
            private LinkedList<Integer> a = new LinkedList<>();
            private LinkedList<Integer> b = new LinkedList<>();
            private LinkedList<Integer> c = new LinkedList<>();

            public void init(int n) {
                for (int i = n; i > 0; i--) {
                    a.addLast(i);
                }
            }

            /**
             * 递归
             * @param n 盘子的个数
             * @param a 起点
             * @param b 中间
             * @param c 终点
             */
            public void move(int n,
                             LinkedList<Integer> a,
                             LinkedList<Integer> b,
                             LinkedList<Integer> c) {
                if (n == 0) {
                    return;
                }
                move(n - 1, a, c, b);  // 把 n - 1 个盘子由a，借c，移至b
                c.addLast(a.removeLast());  // 把最后一个盘子由a 移到c
                CommonUtils.print(a, b, c);
                move(n - 1, b, a, c);  // 把 n - 1 个盘子由b，借a，移至c

            }
        }
        Hanoi hanoi = new Hanoi();
        int target = 3;
        hanoi.init(target);
        LinkedList<Integer> a = hanoi.getA();
        LinkedList<Integer> b = hanoi.getB();
        LinkedList<Integer> c = hanoi.getC();
        hanoi.move(target, a, b, c);
    }

    /**
     * 杨辉三角
     */
    public void triangle(int i) {
        int[][] cache = new int[i][];
        for (int z = 0; z < i; z++) {
            CommonUtils.print(i, z);
            cache = new int[i][z + 1];
            for (int j = 0; j <= z; j++) {
                System.out.print(triangle(cache, z, j) + "    ");
            }
            System.out.println();
        }
    }
    private int triangle(int[][] cache, int i, int j) {
        if (cache[i][j] > 0) {
            return cache[i][j];
        }
        if (j == 0 || i == j) {
            cache[i][j] = 1;
            return 1;
        }
        cache[i][j] = triangle(cache, i - 1, j - 1) + triangle(cache, i - 1, j);
        return cache[i][j];
    }

    /**
     * 杨辉三角 -> 一维数组优化
     */
    public void triangle1(int i) {
        int[] row = new int[i];
        for (int z = 0; z < i; z++) {
            CommonUtils.print(i, z);
            createRow(row,z);
            for (int j = 0; j <= z; j++) {
                System.out.print(row[j] + "    ");
            }
            System.out.println();
        }
    }
    private void createRow(int[] row, int i) {
        if (i == 0 || i == row.length) {
            row[i] = 1;
            return;
        }
        for (int j = i; j > 0; j--) {
            row[j] = row[j] + row[j - 1];
        }
    }


}
